package com.yww.datastructure.queue;

import java.util.Iterator;

/**
 * @author yww
 * @description 环形数组实现队列(head 和 tail 不断递增 ， 用到索引时 ， 再用它们进行计算)
 * @since 2024/2/4 14:55
 */
public class ArrayQueue3<E> implements Queue<E> {
    private final E[] array;
    private int head;
    private int tail;
    private final int capacity;

    public ArrayQueue3(int capacity) {
        // 检查capacity是否是2的幂
        if ((capacity & capacity - 1) != 0) {
            // 让capacity更正位最近的2的幂，算出最接近的次方
            int n = (int) (Math.log10(capacity - 1) / Math.log10(2)) + 1;
            capacity = (int) Math.pow(2, n);
        }
        // capacity就不用预留位置
        this.capacity = capacity;
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail % capacity] = value;
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E val = array[head % capacity];
        head++;
        return val;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E val = array[head % capacity];
        return val;
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public boolean isFull() {
        return tail - head == capacity;
    }

    @Override
    public int size() {
        return tail - head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p  < tail;
            }

            @Override
            public E next() {
                E val = array[p % capacity];
                p++;
                return val ;
            }
        };
    }
}
